package com.lijing.PolandNotation;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
    public static void main(String[] args) {
        //(3+4)*5-6
        String str = "4+4-3*7/5";
//        String suffixExpression = "30 4 + 5 * 6 - ";
//        List<String> list = getListString(suffixExpression);
//        System.out.println(toInfixExpression(str));
//        System.out.println(calculate(list));
        System.out.println("中缀表达式:"+ toInfixExpression(str));
        System.out.println("后缀表达式:"+ toSuffixExpression(toInfixExpression(str)));
        System.out.println(calculate(toSuffixExpression(toInfixExpression(str))));


    }


    //将中缀表达式s转为一个ArrayList
    public static List<String> toInfixExpression(String s){
        List<String> ls = new ArrayList<>();
        char c;
        StringBuilder str;
        int i = 0;
        do{
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57){//c为非数字,则为运算符
                ls.add(c+"");
                i++;
            }else {//考虑多位数
                str = new StringBuilder();
                while(i < s.length() && ((c = s.charAt(i))>= 48 && (c = s.charAt(i)) <=57)){
                    str.append(c);
                    i++;
                }
                ls.add(str.toString());
            }
        }while (i < s.length());
        return ls;
    }
    //将中缀表达式转为后缀表达式需要一个栈s1存储运算符，还需要一个列表存储中间结果
    public static List<String> toSuffixExpression(List<String> s){
        Stack<String> s1 = new Stack<String>();
        List<String> s2 = new ArrayList<String>();
        int i = 0;
        for (String item : s){
            if (item.matches("\\d+")){
                s1.add(item);
            }else if (item.equals("(")){
                s1.push(item);
            }else if (item.equals(")")){//遇到"("时消除一对括号，否则就弹栈入到s2中
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();//弹出左括号
            }else{
                //当item的优先级大于s1栈顶优先级则直接入栈，否则将s1出栈入到s2
                while (s1.size() != 0 && getPriority(s1.peek()) <= getPriority(item)){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        while(s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2;
    }

    //比较优先级
    public static int getPriority(String s){
        int res = 0;
        switch (s){
            case "+":
            case "-":
                res = 1;
                break;
            case "*":
            case "/":
                res = 2;
                break;
            default:
                System.out.println("输入的运算符有误");
                break;
        }
        return res;
    }

    //将一个逆波兰表达式依次将数据和运算符放入ArrayList中
    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分隔
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String elem : split){
            list.add(elem);
        }
        return list;
    }
    //计算
    public static int calculate(List<String> ls){
        Stack<String> stack = new Stack<String>();
        //遍历ls
        for (String str:ls){
            if (str.matches("\\d+")){//匹配的是多位数
                stack.push(str);
            }else {//取出的
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (str.equals("+")){
                    res = num1 + num2;
                }else if (str.equals("-")){
                    res = num1 - num2;
                }else if (str.equals("*")){
                    res = num1 * num2;
                }else if (str.equals("/")){
                    res = num1/num2;
                }else {
                    throw new RuntimeException("operator is wrong!");
                }
                //将res入栈
                stack.push(res+"");
            }

        }
        return Integer.parseInt(stack.pop());
    }
}
